Solution

Approach 1: Use a Hammer (Bruteforce)

Intuition

The straightforward solution is to iterate over all sliding windows and find a maximum for each window. There are N - k + 1 sliding windows and there are k elements in each window, that results in a quite bad time complexity $\mathcal{O}(N k)$.

As you can imagine, this straightforward solution would result in TLE (Time Limit Exceed) exception.

It is correct though, one could start with this solution during the interview and improve it later on.

Implementation

Complexity Analysis

• Time complexity : $\mathcal{O}(N k)$, where N is number of elements in the array.

• Space complexity : $\mathcal{O}(N - k + 1)$ for an output array.
  
  

Approach 2: Deque

Intuition

How one could improve the time complexity? The first idea is to use a heap, since in a maximum heap heap[0] is always the largest element. Though to add an element in a heap of size k costs $\log(k)$, that means $\mathcal{O}(N \log(k))$ time complexity for the solution.

Could we figure out $\mathcal{O}(N)$ solution?

Let's use a deque (double-ended queue), the structure which pops from / pushes to either side with the same $\mathcal{O}(1)$ performance.

It's more handy to store in the deque indexes instead of elements since both are used during an array parsing.

Algorithm

The algorithm is quite straigthforward :

• Process the first k elements separately to initiate the deque.

• Iterate over the array. At each step :

  • Clean the deque :

    • Keep only the indexes of elements from the current sliding window.

    • Remove indexes of all elements smaller than the current one, since they will not be the maximum ones.

  • Append the current element to the deque.

  • Append deque[0] to the output.

• Return the output array.

Implementation

Complexity Analysis

• Time complexity : $\mathcal{O}(N)$, since each element is processed exactly twice - it's index added and then removed from the deque.

• Space complexity : $\mathcal{O}(N)$, since $\mathcal{O}(N - k + 1)$ is used for an output array and $\mathcal{O}(k)$ for a deque.
  
  

Approach 3: Dynamic programming

Intuition

Here is another $\mathcal{O}(N)$ solution. The good thing about this solution is that you don't need any data structures but array / list.

The idea is to split an input array into blocks of k elements. The last block could contain less elements if n % k != 0.

The current sliding window with the first element i and the last element j could be placed inside one block, or in two different blocks.

The situation 1 is simple. Let's use an array left, where left[j] is a maximum element from the beginning of the block to index j, direction left->right.

To work with more complex situation 2, let's introduce array right, where right[j] is a maximum element from the end of the block to index j, direction right->left. right is basically the same as left, but in the other direction.

These two arrays together give all the information about window elements in both blocks. Let's consider a sliding window from index i to index j. By definition, element right[i] is a maximum element for window elements in the leftside block, and element left[j] is a maximum element for window elements in the rightside block. Hence the maximum element in the sliding window is max(right[i], left[j]).

Algorithm

The algorithm is quite straightforward :

• Iterate along the array in the direction left->right and build an array left.

• Iterate along the array in the direction right->left and build an array right.

• Build an output array as max(right[i], left[i + k - 1]) for i in range (0, n - k + 1).

Implementation

1 / 6

Complexity Analysis

• Time complexity : $\mathcal{O}(N)$, since all we do is 3 passes along the array of length N.

• Space complexity : $\mathcal{O}(N)$ to keep left and right arrays of length N, and output array of length N - k + 1.